#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#pragma once
#pragma warning(disable:4996)
typedef long long ll;
using namespace std;
const int M = 3;                  //B树的最小度数
const int KEY_MAX = 2 * M - 1;        //节点包含关键字的最大个数
const int KEY_MIN = M - 1;          //非根节点包含关键字的最小个数
const int CHILD_MAX = KEY_MAX + 1;  //孩子节点的最大个数
const int CHILD_MIN = KEY_MIN + 1;  //孩子节点的最小个数
int Node_All[4] = { 0,0,0,0 };
int ct_All[4] = { 0,0,0,0 };
int rootID[4] = { -1,-1,-1,-1 };
int all = 0;//代表书种类
string filename = "data.dat";
string datafile[4] = { "isbn2num.dat","name2num.dat","author2num.dat","publisher2num.dat" };
string allfile[4] = { "isbnall.dat","nameall.dat","authorall.dat","publisherall.dat" };
string ctfile[3] = { "namect.dat","authorct.dat","publisherct.dat" };
#define tiaojian (strcmp(bks[0].name,name.c_str())==0&&strcmp(bks[0].AuthorName,Authorname.c_str())==0&&strcmp(bks[0].Publisher,Publisher.c_str())==0&&bks[0].price==price)
typedef struct {
	int BookID;
	char name[20];
	char AuthorName[20];
	char Publisher[20];
	int SumBook;//该本书的库存
	char ISBN[14];//ISBN的位数是13位
	bool exist;
	double price;
}Book;
struct mmap {
	int posNum;
	int posValue[10];
};
struct Node
{
	bool isLeaf;             //是否是叶子节点
	int ID;
	int keyNum;              //节点包含的关键字数量
	char keyValue[KEY_MAX][20];     //关键字的值数组
	mmap pos[KEY_MAX];//位置
	int pChild[CHILD_MAX]; //文件指针数组

};
mmap mmapequal(mmap a) {
	mmap mp;
	mp.posNum = a.posNum;
	memcpy(mp.posValue, a.posValue, sizeof(a.posValue));
	return mp;
}
struct valNode {
	char value[20];
	int pos;
};
Node* createNode(int p) {
	Node* nd = new Node();
	nd->ID = Node_All[p];
	nd->keyNum = 0;
	nd->isLeaf = true;
	Node_All[p]++;
	fstream file;
	file.open(datafile[p], ios::binary | ios::app);
	file.write((char*)nd, sizeof(Node));
	file.close();
	return nd;
}
void writeall() {
	fstream f;
	f.open("all.dat", ios::out);
	f << all;
	f.close();
}
void getall() {
	fstream f;
	f.open("all.dat", ios::binary | ios::in);
	if (!f.is_open()) {
		all = 0;
		f.close();
		f.open("all.dat", ios::binary | ios::out);
	}
	if (f.eof())
	{
		all = 0;
		f.close();
		f.open("all.dat", ios::binary | ios::out);
	}
	else f >> all;
	f.close();
}
void get_rootID() {//获得根节点位置
	for (int i = 0;i < 4;i++) {
		fstream ff;
		ff.open(allfile[i], ios::binary | ios::in);
		if (!ff.is_open()) {
			rootID[i] = -1;
			Node_All[i] = 0;
			ct_All[i] = 0;
			ff.close();
			ff.open(allfile[i], ios::binary | ios::out);
		}
		else ff >> rootID[i] >> Node_All[i] >> ct_All[i];
		if (Node_All[i] == 0) {
			rootID[i] = -1;
			Node_All[i] = 0;
			ct_All[i] = 0;
		}
		ff.close();
	}

}
void write_rootId() {
	for (int i = 0;i < 4;i++) {
		fstream f;
		f.open(allfile[i], ios::out);
		f << rootID[i] << " " << Node_All[i] << " " << ct_All[i];
		f.close();
	}

}
void init() {//包括getall和写rootID
	getall();
	get_rootID();
}

Node* getNode(int pNodeID, int p) {
	if (pNodeID >= Node_All[p] || pNodeID < 0) return NULL;
	Node* node = new Node();
	fstream f(datafile[p], ios::in | ios::out | ios::binary);
	f.seekg(pNodeID * sizeof(Node), ios::beg);
	f.read((char*)node, sizeof(Node));
	f.close();
	/*FILE* f = fopen(datafile[p].c_str(), "rb+");
	fseek(f, pNodeID * sizeof(Node), SEEK_SET);
	fread((char*)node, sizeof(Node), 1, f);
	fclose(f);*/
	return node;
}
void changeNodeFile(Node* nd, int p) {
	fstream f(datafile[p], ios::in | ios::out | ios::binary);
	f.seekp(sizeof(Node) * nd->ID, ios::beg);
	f.write((char*)nd, sizeof(Node));
	f.close();
	/*FILE* f = fopen(datafile[p].c_str(), "rb+");
	fseek(f, sizeof(Node) * nd->ID , SEEK_SET);
	fwrite((char*)nd, sizeof(Node), 1, f);
	fclose(f);*/
}
class CBTree
{
public:
	CBTree(int p)
	{
		if (rootID[p] == -1)
			m_pRoot = NULL;
		else m_pRoot = getNode(rootID[p], p);
		//cout << rootID;
		//if(rootID!=-1)
		//	cout << m_pRoot->ID << " " << m_pRoot->isLeaf << " " << m_pRoot->keyNum << " " << m_pRoot->num;
	}

	void addnum(int pNodeID, const char key[], int num, int p) {
		if (pNodeID > Node_All[p] || pNodeID < 0)  //检测节点指针是否为空，或该节点是否为叶子节点
		{
			cout << "添加失败！" << endl;
			return;
		}
		else
		{
			int i;
			Node* pNode = getNode(pNodeID, p);
			for (i = 0; i < pNode->keyNum && strcmp(key, pNode->keyValue[i])>0; ++i)//找到使key<=pNode->keyValue[i]成立的最小下标i
			{
			}
			if (i < pNode->keyNum && strcmp(key, pNode->keyValue[i]) == 0)
			{
				if (pNode->pos[i].posNum < 10) {
					pNode->pos[i].posValue[pNode->pos[i].posNum] = num;
					pNode->pos[i].posNum++;
				}
				else {
					valNode vnd;
					vnd.pos = num;
					strcpy(vnd.value, key);
					fstream f;
					f.open(ctfile[p - 1], ios::binary | ios::app);
					f.write((char*)&vnd, sizeof(vnd));
					f.close();
					ct_All[p]++;
				}
			}
			else
			{
				if (pNode->isLeaf)   //检查该节点是否为叶子节点
				{
					cout << "找不到" << endl;
					return;
				}
				else
				{
					addnum(pNode->pChild[i], key, num, p);
				}
			}
			changeNodeFile(pNode, p);
		}

	}
	//insert() haved checked over
	bool insert(const char key[], int num, int p)    //向B数中插入新结点key
	{
		if (contain(key, p))  //检查该关键字是否已经存在
		{
			addnum(rootID[p], key, num, p);
			return true;
		}
		else
		{
			if (rootID[p] == -1)//检查是否为空树
			{
				m_pRoot = createNode(p);
				rootID[p] = m_pRoot->ID;
			}

			if (m_pRoot->keyNum == KEY_MAX) //检查根节点是否已满
			{
				Node* pNode = createNode(p);
				pNode->pChild[0] = m_pRoot->ID;
				splitChild(pNode, 0, m_pRoot, p);
				m_pRoot = pNode;  //更新根节点指针
				rootID[p] = pNode->ID;
				//changeNodeFile(pNode);
				//changeNodeFile(m_pRoot);
			}

			insertNonFull(m_pRoot, key, num, p);
			//changeNodeFile(m_pRoot);
			return true;
		}
	}
	bool contain(const char key[], int p)const   //检查该key是否存在于B树中 
		//contain()have checked over
		//contain()have checked over
	{
		if (search(rootID[p], key, p) == NULL) return false;
		return true;
	}

	//查找关键字search()have checked over
	mmap* search(int pNodeID, const char key[], int p)const
	{
		if (pNodeID > Node_All[p] || pNodeID < 0)  //检测节点指针是否为空，或该节点是否为叶子节点
		{
			return NULL;
		}
		else
		{
			int i;
			Node* pNode = getNode(pNodeID, p);
			for (i = 0; i < pNode->keyNum && strcmp(key, pNode->keyValue[i])>0; ++i)//找到使key<=pNode->keyValue[i]成立的最小下标i
			{
			}
			if (i < pNode->keyNum && strcmp(key, pNode->keyValue[i]) == 0)
			{
				return &pNode->pos[i];
			}
			else
			{
				if (pNode->isLeaf)   //检查该节点是否为叶子节点
				{
					return NULL;
				}
				else
				{
					return search(pNode->pChild[i], key, p);
				}
			}
		}
	}
	void deletePos(int pNodeID, const char key[], int p, int pos)const
	{
		if (pNodeID > Node_All[p] || pNodeID < 0)  //检测节点指针是否为空，或该节点是否为叶子节点
		{
			return;
		}
		else
		{
			int i;
			Node* pNode = getNode(pNodeID, p);
			for (i = 0; i < pNode->keyNum && strcmp(key, pNode->keyValue[i])>0; ++i)//找到使key<=pNode->keyValue[i]成立的最小下标i
			{
			}
			if (i < pNode->keyNum && strcmp(key, pNode->keyValue[i]) == 0)
			{
				mmap posm = pNode->pos[i];
				for (int j = 0;j < pNode->pos[i].posNum;j++) {
					if (pNode->pos[i].posValue[j] == pos) pNode->pos[i].posValue[j] = -1;
				}
				changeNodeFile(pNode, p);
				return;
			}
			else
			{
				if (pNode->isLeaf)   //检查该节点是否为叶子节点
				{
					return;
				}
				else
				{
					deletePos(pNode->pChild[i], key, p, pos);
				}
			}
		}
	}

	//分裂子节点 have checked over
	void splitChild(Node* pParent, int nChildIndex, Node* pChild, int p)
	{
		//将pChild分裂成pLeftNode和pChild两个节点
		Node* pRightNode = createNode(p);//分裂后的右节点
		pRightNode->isLeaf = pChild->isLeaf;
		pRightNode->keyNum = KEY_MIN;
		int i;
		for (i = 0; i < KEY_MIN; ++i)//拷贝关键字的值
		{
			strcpy(pRightNode->keyValue[i], pChild->keyValue[i + CHILD_MIN]);
			pRightNode->pos[i] = mmapequal(pChild->pos[i + CHILD_MIN]);
		}
		if (!pChild->isLeaf)  //如果不是叶子节点，拷贝孩子节点指针
		{
			for (i = 0; i < CHILD_MIN; ++i)
			{
				pRightNode->pChild[i] = pChild->pChild[i + CHILD_MIN];
			}
		}

		pChild->keyNum = KEY_MIN;  //更新左子树的关键字个数

		for (i = pParent->keyNum; i > nChildIndex; --i)//将父节点中的nChildIndex后的所有关键字的值和子树指针向后移一位
		{
			pParent->pChild[i + 1] = pParent->pChild[i];
			strcpy(pParent->keyValue[i], pParent->keyValue[i - 1]);
			pParent->pos[i] = mmapequal(pParent->pos[i - 1]);
		}
		++pParent->keyNum;  //更新父节点的关键字个数
		pParent->pChild[nChildIndex + 1] = pRightNode->ID;  //存储右子树指针
		strcpy(pParent->keyValue[nChildIndex], pChild->keyValue[KEY_MIN]);
		pParent->pos[nChildIndex] = mmapequal(pChild->pos[KEY_MIN]);

		pParent->isLeaf = false;
		changeNodeFile(pRightNode, p);
		changeNodeFile(pParent, p);
		changeNodeFile(pChild, p);
	}

	//在非满节点中插入关键字 insertNonFull have checked over
	void insertNonFull(Node* pNode, const char key[], int num, int p)
	{
		int i = pNode->keyNum;  //获取节点内关键字个数
		if (pNode->isLeaf)      //pNode是叶子节点
		{
			while (i > 0 && strcmp(pNode->keyValue[i - 1], key) > 0)   //从后往前，查找关键字的插入位置
			{
				strcpy(pNode->keyValue[i], pNode->keyValue[i - 1]);
				pNode->pos[i] = mmapequal(pNode->pos[i - 1]);
				//向后移位
				--i;
			}

			strcpy(pNode->keyValue[i], key);  //插入关键字的值
			pNode->pos[i].posValue[0] = num;
			pNode->pos[i].posNum = 1;
			++pNode->keyNum; //更新节点关键字的个数
			changeNodeFile(pNode, p);
		}
		else//pNode是内节点
		{
			while (i > 0 && strcmp(pNode->keyValue[i - 1], key) > 0)   //从后往前，查找关键字的插入的子树
				--i;
			Node* pChild = getNode(pNode->pChild[i], p); //目标子树结点指针 
			if (pChild->keyNum == KEY_MAX)  //子树节点已满
			{
				splitChild(pNode, i, pChild, p);//分裂子树节点
				if (strcmp(key, pNode->keyValue[i]) > 0)   //确定目标子树
					pChild = getNode(pNode->pChild[i + 1], p);
			}
			insertNonFull(pChild, key, num, p);  //插入关键字到目标子树节点
			changeNodeFile(pChild, p);
		}
		changeNodeFile(pNode, p);
	}

private:
	Node* m_pRoot;  //B树的根节点
};
void showBook(vector<Book> b)
{
	if (b.empty()) {
		cout << "*抱歉，书库中暂时找不到相关书籍！" << endl;
		return;
	}
	int i = 1;
	for (vector<Book>::iterator book = b.begin(); book != b.end(); ++book)
	{
		cout << "编号:" << i << endl;
		cout << "ISBN:" << (*book).ISBN << endl;
		cout << "ID:" << (*book).BookID << endl;
		cout << "书名:" << (*book).name << endl;
		cout << "作者:" << (*book).AuthorName << endl;
		cout << "出版社:" << (*book).Publisher << endl;
		cout << "馆藏量:" << (*book).SumBook << endl;
		cout << "价格：" << (*book).price << endl;
		cout << "**********************************************************" << endl;
		i++;
	}
}
vector<Book> FindBookById(int BookID)
{
	vector<Book> bookshelf;
	if (BookID >= all || BookID < 0) {
		cout << "查无此书。" << endl;
		return bookshelf;
	}
	Book bk;
	fstream f(filename, ios::in | ios::out | ios::binary);
	f.seekg(BookID * sizeof(Book), ios::beg);
	f.read((char*)&bk, sizeof(Book));
	f.close();
	if (bk.BookID != BookID) bk.BookID = BookID;
	if (bk.exist)
		bookshelf.push_back(bk);
	return bookshelf;
}
vector<Book> findBookByISBN(string ISBN) {
	CBTree* tree = new CBTree(0);
	vector<Book> bkshelf;
	mmap* res = tree->search(rootID[0], ISBN.c_str(), 0);
	if (res == NULL) return bkshelf;
	else return FindBookById(res->posValue[0]);
}
void deleteBookByValue(string value, int p, int pos) {
	CBTree* tree = new CBTree(p);
	tree->deletePos(rootID[p], value.c_str(), p, pos);
}
vector<Book> findBookByValue(string value, int p) {//p=1,name;p=2,author;p=3,pub
	CBTree* tree = new CBTree(p);
	vector<Book> bkshelf;
	mmap* res = tree->search(rootID[p], value.c_str(), p);
	if (res == NULL) return bkshelf;
	else {
		for (int i = 0;i < res->posNum;i++) {
			vector<Book> bks = FindBookById(res->posValue[i]);
			if (bks.size() > 0) bkshelf.push_back(bks[0]);
		}
	}
	fstream f;
	int i = 0;
	valNode vnd;
	f.open(ctfile[p - 1], ios::binary | ios::in);
	if (f.is_open()) {
		for (int i = 0;i < ct_All[p];i++) {
			f.read((char*)&vnd, sizeof(vnd));
			if (strcmp(vnd.value, value.c_str()) == 0) {
				vector<Book> bks = FindBookById(vnd.pos);
				if (bks.size() > 0) bkshelf.push_back(bks[0]);
			}
		}
		f.close();
	}
	f.close();
	return bkshelf;
}
string rcuu(string a1, int b1)//容错
{
	int RIGHT1 = 0;
	int RIGHT2 = 0;
	while (!(RIGHT1 && RIGHT2))
	{
		if (a1.size() > b1)
		{
			RIGHT1 = 0;
		}
		else
		{
			RIGHT1 = 1;
			for (int i = 0;i < a1.size();i++)
			{
				if (a1[i] == ' ')
				{
					RIGHT2 = 0;
					break;
				}
				RIGHT2 = 1;
			}
		}
		if (!(RIGHT1 && RIGHT2))
		{
			cout << "名字不能包含空格且不能超过十四个字符，请重新输入：";
			getline(cin, a1);
		}
	}
	return a1;
}
void end() {
	writeall();
	write_rootId();
}
bool isISBN(string ISBN) {
	if (ISBN.size() != 13) return false;
	else {
		for (int i = 0;i < 13;i++) {
			if (ISBN[i] < '0' || ISBN[i]>'9') return false;
		}
	}
	return true;
}
void addBooks() {//自用加书！
	system("cls");
	//freopen("testadd.txt", "r", stdin);
	cout << "************************************加书***********************************" << endl;
	int cnt;
	cout << "*请输入要添加的书的种类数：" << endl;
	cin >> cnt;//
	while (cnt <= 0 || cin.fail()) {
		cin.clear();
		cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
		cout << "*输入错误，请重新输入！" << endl;
		cin >> cnt;
	}
	cin.ignore();// .
	string ISBN;//
	string name;
	string Authorname;
	string Publisher;
	int SumBook;//书的数量之和
	double price;
	Book bk;
	fstream file;
	for (int i = 1;i <= cnt;) {
		system("cls");
		cout << "*请输入书籍详细信息：" << endl;
		//showBook(FindBookById(11));
		cout << "*第" << i << "种 共" << cnt << "种：" << endl;
		cout << "*ISBN:(13位且不能包括空格）" << endl;;
		getline(cin, ISBN);
		while (!isISBN(ISBN)) {
			cout << "*输入错误，请重新输入！" << endl;
			getline(cin, ISBN);
		}
		cout << "书名:(19字符以内)" << endl;;getline(cin, name);
		while (name.size() >= 20 || name.size() <= 0) {
			cout << "*输入错误，请重新输入！" << endl;
			getline(cin, name);
		}
		cout << "作者:(19字符以内)" << endl;getline(cin, Authorname);
		while (Authorname.size() >= 20 || Authorname.size() <= 0) {
			cout << "*输入错误，请重新输入！" << endl;
			getline(cin, Authorname);
		}
		cout << "出版社:(19字符以内)" << endl;;getline(cin, Publisher);
		while (Publisher.size() >= 20 || Publisher.size() <= 0) {
			cout << "*输入错误，请重新输入！" << endl;
			getline(cin, Publisher);
		}
		cout << "增加量:" << endl;cin >> SumBook;
		while (SumBook <= 0 || cin.fail()) {
			cin.clear();
			cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
			cout << "*输入错误，请重新输入！" << endl;
			cin >> SumBook;
		}
		cout << "价格:" << endl;;cin >> price;
		while (price <= 0 || cin.fail()) {
			cin.clear();
			cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
			cout << "*输入错误，请重新输入！" << endl;
			cin >> price;
		}
		cin.ignore();
		vector<Book> bks = findBookByISBN(ISBN);
		if (bks.size() > 0) {
			if (ISBN == string(bks[0].ISBN) && bks[0].exist) {
				if (!tiaojian) {
					cout << "*图书录入信息错误，请检查输入信息后重新输入" << endl;
					cout << "*详细：书库中已有该ISBN的书，但与输入信息不匹配" << endl;
					system("pause");
					continue;
				}
				cout << "*书库中已有该书，仅为您增加库存" << endl;
				bks[0].SumBook += SumBook;
				fstream f(filename, ios::in | ios::out | ios::binary);
				f.seekp(sizeof(Book) * bks[0].BookID, ios::beg);
				f.write((char*)&bks[0], sizeof(Book));
				f.close();
				system("pause");
				/*FILE* f = fopen(filename.c_str(), "rb+");
				fseek(f, sizeof(Book) * bks[0].BookID, SEEK_SET);
				fwrite((char*)&bks[0], sizeof(Book), 1, f);
				fclose(f);*/
			}
		}
		else {
			strcpy(bk.AuthorName, Authorname.c_str());
			strcpy(bk.ISBN, ISBN.c_str());
			strcpy(bk.name, name.c_str());
			strcpy(bk.Publisher, Publisher.c_str());
			bk.SumBook = SumBook;
			bk.BookID = all;
			bk.exist = true;
			bk.price = price;
			file.open(filename, ios::binary | ios::app);
			file.write((char*)&bk, sizeof(Book));
			file.close();
			all++;
			CBTree* tree0 = new CBTree(0);
			tree0->insert(bk.ISBN, bk.BookID, 0);
			CBTree* tree1 = new CBTree(1);
			tree1->insert(bk.name, bk.BookID, 1);
			CBTree* tree2 = new CBTree(2);
			tree2->insert(bk.AuthorName, bk.BookID, 2);
			CBTree* tree3 = new CBTree(3);
			tree3->insert(bk.Publisher, bk.BookID, 3);
			end();
		}
		i++;
	}
	file.close();
}

bool cmp(pair<Book, int> a, pair<Book, int> b) {
	return a.second > b.second;
}
vector<Book> fuzzy(string str) {//娣峰悎灞炴€фā绯婃煡鎵撅紝鐢ㄦ埛鍙嚜琛岃緭鍏ュ弬鏁帮紝浠ョ┖鏍煎垎闅?
	double k = 0.5;//妯＄硦鎼滅储搴?
	vector<Book> bkshelf;
	vector<string> sub;
	int loc = 0;
	while (str.size() > 0 && loc >= 0) {
		loc = str.find(' ');
		sub.push_back(str.substr(0, loc));
		str = str.substr(loc + 1);
	}
	vector<pair<Book, int>> bkm;
	for (int i = 0;i < all;i++) {
		vector<Book> bk = FindBookById(i);
		int m = 0;//璁℃暟
		if (bk.size() > 0) {
			for (int j = 0;j < sub.size();j++) {
				if (strstr(bk[0].name, sub[j].c_str()) != NULL)
					m++;
				if (strstr(bk[0].AuthorName, sub[j].c_str()) != NULL)
					m++;
				if (strstr(bk[0].Publisher, sub[j].c_str()) != NULL)
					m++;
			}
			if (m / (double)sub.size() >= k) bkm.push_back(make_pair(bk[0], m));
		}
	}
	sort(bkm.begin(), bkm.end(), cmp);
	for (int i = 0;i < bkm.size();i++)
		bkshelf.push_back(bkm[i].first);
	return bkshelf;
}